package com.linyaonan.leetcode.medium._275;

/**
 * 给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。
 *
 * h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次。
 *
 * 请你设计并实现对数时间复杂度的算法解决此问题。
 *
 *
 *
 * 示例 1：
 *
 * 输入：citations = [0,1,3,5,6]
 * 输出：3
 * 解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
 *      由于研究者有3篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3 。
 * 示例 2：
 *
 * 输入：citations = [1,2,100]
 * 输出：2
 *
 *
 * 提示：
 *
 * n == citations.length
 * 1 <= n <= 10^5
 * 0 <= citations[i] <= 1000
 * citations 按 升序排列
 *
 * @author: Lin
 * @date: 2024/12/12
 */
public class HIndexII {

    /**
     * 以这个分析citations = [0,1,3,5,6]，一共5篇论文，那么最大的引用次数就是5，最小的引用次数0
     * 所以从 index = 0 -> length - 1 进行二分
     *
     * if cit[index] <= length - index 则表示满足
     *
     * @param citations
     * @return
     */
    public int hIndex(int[] citations) {
        if (citations.length == 0) {
            return 0;
        }
        //     {1,2,3,4,8,12,15,18,20,21,23,30,39,41,45,46,48,50,52,100}
        //索引 {0,1,2,3,4,5, 6, 7, 8, 9, 10,11,12,13,14,15,16,17,18,19}
        int l = 1;
        int r = citations.length;
        int rr = 0;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (m <= citations[citations.length - m]) {
                rr = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        return rr;
    }

}
